package leetcode.weekly.week331;

//Solution3Test
public class Solution3 {

	public int minCapability(int[] nums, int k) {
		int l = (int) 1e9 + 1, r = 0;
		for (int num : nums) {
			l = Math.min(num, l);
			r = Math.max(num, r);
		}
		int len = nums.length;
		int ans = 0;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			int[][] dp = new int[len][2];// 0 没偷 ，1 偷了
			dp[0][0] = 0;
			dp[0][1] = nums[0] <= m ? 1 : 0;
			for (int i = 1; i < len; i++) {
				int num = nums[i];
				dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
				if (num <= m) {
					dp[i][1] = dp[i - 1][0] + 1;
				}
			}
			boolean can = Math.max(dp[len - 1][0], dp[len - 1][1]) >= k;
			if (can) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}
}
